//如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也
//视作摆动序列。 
//
// 
// 
// 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。 
// 
// 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一
//个差值为零。 
// 
//
// 子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。 
//
// 给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,7,4,9,2,5]
//输出：6
//解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。
// 
//
// 示例 2： 
//
// 
//输入：nums = [1,17,5,10,13,15,10,5,16,8]
//输出：7
//解释：这个序列包含几个长度为 7 摆动序列。
//其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。
// 
//
// 示例 3： 
//
// 
//输入：nums = [1,2,3,4,5,6,7,8,9]
//输出：2
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 1000 
// 0 <= nums[i] <= 1000 
// 
//
// 
//
// 进阶：你能否用 O(n) 时间复杂度完成此题? 
// Related Topics 贪心 数组 动态规划 
// 👍 548 👎 0

package com.cute.leetcode.editor.cn;

import java.util.Arrays;

public class WiggleSubsequence {
    public static void main(String[] args) {
        new WiggleSubsequence().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 使用dp存储以当前数字结尾的最长摆动数列的长度，默认长度为1
     */
    class Solution {
        public int wiggleMaxLength(int[] nums) {
            int len = nums.length;
            if (len == 1) return 1;
            int[] dp =  new int[len];//存储以当前数字结尾的摆动数列的长度
            Arrays.fill(dp, 1);
            int res = 1;
            for (int i = 1; i < len; i++) {
                for (int j = i-1; j >=0; j--) {
                    if (j == 0){//如果到了第一个元素直接比较是否相等
                        if(nums[i] != nums[j])
                            dp[i] = Math.max(dp[i],2);
                    }else {
                        if ((nums[i]-nums[j])*(nums[j]-nums[j-1])<0)//判断是否为抖动序列
                            dp[i] = Math.max(dp[i],dp[j]+1);
                    }
                }
                res = Math.max(res, dp[i]);
            }
            return res;
        }

        /**
         * 另一种dp，使用down和up数组保存长度，
         * 假设 up[i] 表示 nums[0:i] 中最后两个数字递增的最长摆动序列长度
         * down[i] 表示 nums[0:i] 中最后两个数字递减的最长摆动序列长度
         * 只有一个数字时默认为 1。
         *  当nums[i+1] > nums[i]
         *  假设 down[i] 表示的最长摆动序列的最远末尾元素下标正好为 i
         *  遇到新的上升元素后，up[i+1] = down[i] + 1
         *  这是因为 up 一定从 down 中产生（初始除外），并且 down[i] 此时最大。
         *  假设 down[i] 表示的最长摆动序列的最远末尾元素下标小于 i，设为 j
         *  那么 nums[j:i] 一定是递增的，因为若完全递减，最远元素下标等于 i
         *  若波动，那么 down[i] > down[j]。由于 nums[j:i] 递增，down[j:i] 一直等于 down[j]
         *  依然满足 up[i+1] = down[i] + 1 。
         *  因为只关心up[i] 和 down[i] 所以可以使用滚动变量（更方便）
         *  比如
         *  nums : 1↑7↓4↑5↑6↓2↑8
         *  up :   1  2  2  4  4  4  6
         *  down:  1  1  3  3  3  5  5
         * up 和 down有一个元素时默认为1
         *
         */
        public int wiggleMaxLength2(int[] nums) {
            int len = nums.length;
            int up = 1;
            int down = 1;
            for (int i = 1; i < len; i++) {
                if (nums[i] > nums[i-1]) up = down+1;//末尾递增
                else if (nums[i] < nums[i-1]) down = up+1;//末尾递减
            }
            return len == 0 ? 0 : Math.max(up, down);
        }

        //二刷的时候和一刷中的题解思路一致
        //代码随想录的题解，统计峰值数量来进行判断
        //想要保持波动的话，忽略掉单调区间的元素
        public int wiggleMaxLength3(int[] nums) {
            int res = 1;//为了统计边界
            int curDiff,preDiff = 0;
            for (int i = 0; i < nums.length-1; i++) {
                curDiff = nums[i+1]-nums[i];
                if ((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff <0)){
                    res++;
                    preDiff = curDiff;
                }
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}